UVa/10090 - Marbles/10090.cpp

   1 /*
   2   Accepted
   3  */
   4 using namespace std;
   5 #include <cstdio>
   6 #include <climits>
   7 #include <cassert>
   8 #include <algorithm>
   9
  10 long long get_gcd(long long a, long long b, long long &x, long long &y){
  11   if (b > a) return get_gcd(b, a, y, x);
  12   if (b == 0){
  13     x = 1, y = 0;
  14     return a;
  15   }
  16   long long g, sub_x, sub_y;
  17   g = get_gcd(b, a%b, sub_x, sub_y);
  18   x = sub_y, y = sub_x - sub_y*(a/b);
  19   return g;
  20 }
  21
  22 int main(){
  23   long long n, n1, n2, c1, c2;
  24   while (scanf("%lld", &n)==1 && n){
  25     scanf("%lld %lld %lld %lld", &c1, &n1, &c2, &n2);
  26
  27     long long a, b, gcd;
  28     gcd = get_gcd(n1, n2, a, b);
  29
  30     if (n % gcd != 0){
  31       printf("failed\n");
  32     }else{
  33       a *= (n/gcd), b *= (n/gcd);
  34       assert(a*n1 + b*n2 == n);
  35
  36
  37       long long lcm = n1/gcd*n2;
  38       long long inc_a = lcm/n1, inc_b = lcm/n2;
  39
  40       if (a < 0){
  41         long long times = -a/inc_a;
  42         if (-a % inc_a) ++times;
  43         a += times*inc_a, b -= times*inc_b;
  44       }
  45
  46       if (b < 0){
  47         long long times = -b/inc_b;
  48         if (-b % inc_b) ++times;
  49         b += times*inc_b, a -= times*inc_a;
  50       }
  51
  52
  53
  54       if (a < 0 || b < 0) printf("failed\n");
  55       else{
  56
  57         if (a > b && b >= inc_b){
  58           long long times = b/inc_b;
  59           a += times*inc_a, b -= times*inc_b;
  60         }
  61
  62         else if (b > a && a >= inc_a){
  63           long long times = a/inc_a;
  64           a -= times*inc_a, b += times*inc_b;
  65         }
  66
  67
  68         pair<long long, long long> ans;
  69         long long best = LLONG_MAX;
  70
  71         //Listo, tenemos una posible solución.
  72         if (a*c1 + b*c2 < best){
  73           best = a*c1 + b*c2;
  74           ans = make_pair(a, b);
  75         }
  76
  77         //Ahora bajemos esto al otro extremo
  78         if (a > b){
  79           //Bajemos a
  80           long long times = a/inc_a;
  81           a -= times*inc_a, b += times*inc_b;
  82
  83           if (a*c1 + b*c2 < best){
  84             best = a*c1 + b*c2;
  85             ans = make_pair(a, b);
  86           }
  87
  88         }else{
  89           //Bajemos b
  90           long long times = b/inc_b;
  91           a += times*inc_a, b -= times*inc_b;
  92           if (a*c1 + b*c2 < best){
  93             best = a*c1 + b*c2;
  94             ans = make_pair(a, b);
  95           }
  96         }
  97
  98
  99         printf("%lld %lld\n", ans.first, ans.second);
 100       }
 101
 102     }
 103   }
 104   return 0;
 105 }